package sliding_window

import "sort"

/*
1004.给定一个二进制数组nums和一个整数k，如果可以翻转最多k个 0 ，则返回 数组中连续 1 的最大个数 。

示例 1：
输入：nums = [1,1,1,0,0,0,1,1,1,1,0], K = 2
输出：6
解释：[1,1,1,0,0,1,1,1,1,1,1]
粗体数字从 0 翻转到 1，最长的子数组长度为 6。

示例 2：
输入：nums = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], K = 3
输出：10
解释：[0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1]
粗体数字从 0 翻转到 1，最长的子数组长度为 10。

*/

/*
前缀和：
对于数组 A 的区间 [left,right] 而言，只要它包含不超过 k 个 0，我们就可以根据它构造出一段满足要求，并且长度为 right−left+1 的区间。
因此，我们可以将该问题进行如下的转化，即：
对于任意的右端点 right，希望找到最小的左端点 left，使得 [left,right] 包含不超过 k个 0。
只要我们枚举所有可能的右端点，将得到的区间的长度取最大值，即可得到答案。

要想快速判断一个区间内 0 的个数，我们可以考虑将数组 A 中的 0 变成 1，1 变成 0。此时，我们对数组 A 求出前缀和，记为数组 P，
那么 [left,right] 中包含不超过 k 个 1（注意这里就不是 0 了），当且仅当二者的前缀和之差：
P[right]−P[left−1] 小于等于 k。这样一来，我们就可以容易地解决这个问题了。

二分查找：
前缀和数组P
P[right]-P[left-1] <= k
等价于
P[left-1] >= P[right]-k
也就是说，我们需要找到最小的满足上述等式的left,由于数组A中仅包含0/1，因此前缀和数组是一个单调递增的数组，我们就可以使用二分查找的方法得到left,
由于上述等式中，左侧的下标是left-1而不是left,因此我们在构造前缀和数组时，可以将前缀和整体向右移动一位，空出P[0]的位置。即：
P[0]=0
P[i]=P[i-1]+(1-A[i-1])
此时，我们在数组P上二分查找的下标即为left本身，同时我们也避免了原先left=0时，left-1=-1不在数组合法的下标范围中的边界情况
*/
//时间复杂度：O(nlogn)，其中 n是数组 A 的长度。每一次二分查找的时间复杂度为 O(logn)，我们需要枚举 right 进行 n 次二分查找，因此总时间复杂度为 O(nlogn)。
//空间复杂度：O(n)，即为前缀和数组 P 需要的空间。
func longestOnesSearch(nums []int, k int) (ans int) {
	n := len(nums)
	p := make([]int, n+1)
	for i, v := range nums {
		p[i+1] = p[i] + 1 - v
	}
	for right, v := range p {
		left := sort.SearchInts(p, v-k)
		ans = max(ans, right-left)
	}
	return
}

/*
 前缀和+滑动窗口
 等式：P[left-1] >= P[right]-k
 观察上述等式，由于前缀和数组P是单调递增的，那么等式右侧P[right]-k同样也是单调递增的，因此我们可以发现：
 随着right的增大，满足上述等式的最小的 left 值是单调递增的。
 这样一来我们就可以利用滑动窗口来实时地维护left和right了。在right右移动的过程中，我们同步移动left,直到left为首个（即最小的）满足等式的位置。
 我们就可以对答案进行更新了。
 当我们利用滑动窗口代替二分查找解决本问题时，就不需要显式的计算并保存出前缀和数组了。我们只需要知道left和right作为下标在前缀和数组中对应的值。
 因此我们只需要用两个变量lsum和rsum 记录left和right 分别对应的前缀和即可。
*/
func longestOnes(nums []int, k int) (ans int) {
	left, lsum, rsum := 0, 0, 0
	for right, v := range nums {
		rsum += 1 - v //P[i]=P[i-1]+(1-A[i-1])
		for lsum < rsum-k {
			lsum += 1 - nums[left]
			left++
		}
		ans = max(ans, right-left+1)
	}
	return
}

//滑动窗口模板方法
func longestOnesSW(nums []int, k int) (res int) {
	left, right, zeroNum := 0, 0, 0
	//expand window
	for right < len(nums) {

		if nums[right] == 0 {
			zeroNum++
		}
		right++

		//shrink window 可以翻转最多k个0
		for zeroNum > k {
			if nums[left] == 0 {
				zeroNum--
			}
			left++
		}
		res = max(res, right-left)
	}
	return
}

/*
Find the longest subarray size with at most K zeros.

Explanation:
For each A[j], try to find the longest subarray.
If A[i] ~ A[j] has zeros <= K, we continue to increment j.
If A[i] ~ A[j] has zeros > K, we increment i (as well as j).
*/
func longestOnesSuper(a []int, k int) int {
	i, j := 0, 0
	for j = 0; j < len(a); j++ {
		if a[j] == 0 {
			k--
		}
		//at most k zeros,so k++,i++
		if k < 0 && a[i] == 0 {
			k++
			i++
		}
	}
	return j - i
}
